﻿#define _CRT_SECURE_NO_WARNINGS 1
/*问题描述
　　求 2**2023%1000，即 2的2023次方除以1000的余数。
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
  */

/*
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	long long result = 1;
	int x = 1000;

	for (int i = 0; i < 2023; i++) {
		result = (result * 2) % x;//每次都取余，防止溢出
	}

	cout << result;
	return 0;
}*/

/*问题描述
　　如果一个正整数转化成二进制与转换成八进制后所有数位的数字之和相等，则称为数位和相等的数。
　　前几个数位和相等的正整数为 1, 8, 9, 64, ……
　　请问第 23 个数位和相等的正整数是多少？*/

/*
#include<stdio.h>
#include<stdlib.h>

int digitSum(int number) {
    int sum = 0;
    while (number > 0) {
        sum += number % 10;
        number /= 10;
    }
    return sum;
}

//转化为2进制字符串表示
void getBinaryRepresentation(int number, char binary[33]) {
    int i = 0;
    while (number > 0) {
        binary[i]=(number%2)+'0';
        i++;
        number /= 2;
    }
    binary[i]= '\0';//字符串结尾

    // 翻转字符串
    for (int f = 0, r = i - 1; f < r; f++, r--) {
        char temp = binary[f];
        binary[f] = binary[r];
        binary[r] = temp;
    }
}

//转化为8进制字符串表示

// 获取数字的八进制表示字符串
//void getOctalRepresentation(int number, char octalRepresentation[12]) {
 //   sprintf(octalRepresentation, "%o", number);//sprintf函数将数字转化为字符串,%o表示八进制
//}

void getOctalRepresentation(int number, char octal[12]) {
    int i = 0;
    while (number > 0) {
        octal[i]=(number%8)+'0';
        i++;
        number/= 8;
    }
    octal[i]='\0';//字符串结尾

    // 翻转字符串
    for (int f = 0, r = i - 1; f < r; f++, r--) {
		char temp = octal[f];
		octal[f] = octal[r];
		octal[r] = temp;
	}
}

//检查一个十进制数的二进制和八进制的位数和是否相等的函数
int hasEqualDigitSum(int number) {
    char binary[33];
    getBinaryRepresentation(number, binary);

    char octal[12];
    getOctalRepresentation(number, octal);

    int binarySum = digitSum(atoi(binary));
    int octalSum = digitSum(atoi(octal));

    return binarySum == octalSum;
}

int main() {
    int count = 0;
    int number = 1;

    while (count < 23) {
        if (hasEqualDigitSum(number)) {
			count++;
		}
        if (count == 23) {
            printf("%d", number);
        }
        number++;
    }

    return 0;
}
*/


/*问题描述
　　对于以下这些数（6行，每行6个，共36个），请问约数个数最多的是哪个？（如果有多个，请回答出现最早的那个）
　　393353 901440 123481 850930 423154 240461
　　373746 232926 396677 486579 744860 468782
　　941389 777714 992588 343292 385198 876426
　　483857 241899 544851 647930 772403 109929
　　882745 372491 877710 340000 659788 658675
　　296521 491295 609764 718967 842000 670302*/

/*
#include<stdio.h>

//计算一个数的约数个数
int countDivisors(int num) {
    int count = 0;
    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int numbers[6][6] = {
        {393353, 901440, 123481, 850930, 423154, 240461},
        {373746, 232926, 396677, 486579, 744860, 468782},
        {941389, 777714, 992588, 343292, 385198, 876426},
        {483857, 241899, 544851, 647930, 772403, 109929},
        {882745, 372491, 877710, 340000, 659788, 658675},
        {296521, 491295, 609764, 718967, 842000, 670302}
    };

    int maxDivisors = 0;
    int maxDivisorsNumber = 0;

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            int num=numbers[i][j];
            int divisorscount = countDivisors(num);
            if (divisorscount > maxDivisors) {
				maxDivisors=divisorscount;
				maxDivisorsNumber=num;
			}
        }
    }

    printf("约数最多的数是%d,它有%d个约数", maxDivisorsNumber, maxDivisors);
    return 0;
}*/

/*问题描述
　　小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性，每次 2 的上下左右四个相邻的位置中的 0 都会变成 2 。直到最后每个 2 的周围都是 1 或 2 结束。
　　请问，最终矩阵中有多少个 2 ？
　　以下是小蓝的矩阵，共 30 行 40 列。
　　0000100010000001101010101001001100000011
　　0101111001111101110111100000101010011111
　　1000010000011101010110000000001011010100
　　0110101010110000000101100100000101001001
　　0000011010100000111111001101100010101001
　　0110000110000000110100000000010010100011
　　0100110010000110000000100010000101110000
　　0010011010100110001111001101100110100010
　　1111000111101000001110010001001011101101
　　0011110100011000000001101001101110100001
　　0000000101011000010011111001010011011100
　　0000100000011001000100101000111011101100
　　0010110000001000001010100011000010100011
　　0110110000100011011010011010001101011011
　　0000100100000001010000101100000000000010
　　0011001000001000000010011001100101000110
　　1110101000011000000100011001001100111010
　　0000100100111000001101001000001010010001
　　0100010010000110100001100000110111110101
　　1000001001100010011001111101011001110001
　　0000000010100101000000111100110010101101
　　0010110101001100000100000010000010110011
　　0000011101001001000111011000100111010100
　　0010001100100000011000101011000000010101
　　1001111010010110011010101110000000101110
　　0110011101000010100001000101001001100010
　　1101000000010010011001000100110010000101
　　1001100010100010000100000101111111111100
　　1001011010101100001000000011000110110000
　　0011000100011000010111101000101110110001*/


/*
#include <stdio.h>

#define ROWS 30
#define COLS 40

void printMatrix(int matrix[ROWS][COLS]) {
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

void performInfection(int matrix[ROWS][COLS]) {
    // 将第一行和第一列的0变为2
    for (int i = 0; i < ROWS; ++i) {
        if (matrix[i][0] == 0) {
            matrix[i][0] = 2;
        }
    }
    for (int j = 0; j < COLS; ++j) {
        if (matrix[0][j] == 0) {
            matrix[0][j] = 2;
        }
    }

    // 传染性变换
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            if (matrix[i][j] == 2) {
                if (i - 1 >= 0 && matrix[i - 1][j] == 0) {
                    matrix[i - 1][j] = 2;
                }
                if (i + 1 < ROWS && matrix[i + 1][j] == 0) {
                    matrix[i + 1][j] = 2;
                }
                if (j - 1 >= 0 && matrix[i][j - 1] == 0) {
                    matrix[i][j - 1] = 2;
                }
                if (j + 1 < COLS && matrix[i][j + 1] == 0) {
                    matrix[i][j + 1] = 2;
                }
            }
        }
    }
}

int countTwos(int matrix[ROWS][COLS]) {
    int count = 0;
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            if (matrix[i][j] == 2) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int matrix[ROWS][COLS];

    // 用户输入二维矩阵的信息
    
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            scanf("%ld", &matrix[i][j]);
        }
    }

    // 进行变换
    performInfection(matrix);

    // 打印最终矩阵
    //printMatrix(matrix);

    // 统计最终矩阵中2的个数
    int twosCount = countTwos(matrix);

    printf("最终矩阵中2的个数：%d\n", twosCount);

    return 0;
}
*/


/*问题描述
　　给定一个正好六位的正整数 x，请将 x 循环左移一位后输出。
　　所谓循环左移一位，是指将原来的十万位变为个位，原来的万位到个位向左移动依次变为十万位到十位。
　　例如：194910 左移一位变为 949101 。
　　又如：987123 左移一位变为 871239 。
输入格式
　　输入一行包含一个整数 x 。保证输入的 x 正好包含 6 个十进制数位，而且十万位和万位上的数字均不为 0 。
输出格式
　　输出一行包含一个整数，表示答案。
样例输入
194910
样例输出
949101*/


/*
#include <stdio.h>

int main() {
    // 读取输入
    char xstr[7];
    scanf("%s", xstr);

    // 将输入的字符串转换为整数
    int x;
    sscanf(xstr, "%d", &x);

    // 循环左移一位
    int left_shifted = (x % 100000) * 10 + x / 100000;

    // 输出结果
    printf("%d\n", left_shifted);

    return 0;
}*/

/*问题描述
　　输入一个仅包含小写英文字母的字符串，请问这个字符串中的最后一元音是什么。
　　在英文中，a, e, i, o, u 共 5 个字母是元音字母，其它字母不是元音字母。
输入格式
　　输入一行包含一个字符串，仅由小写英文字符组成，字符串中至少包含一个元音字母。
输出格式
　　输出一行包含一个字符，表示答案。
样例输入
lanqiao
样例输出
o
样例输入
cup
样例输出
u
评测用例规模与约定
　　对于所有评测用例，1 <= 字符数量 <= 10000 。*/


/*
#include <stdio.h>

int main() {
    char str[10001];
    scanf("%s", str);

    char last_vowel;
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
            last_vowel = str[i];
        }
    }

    printf("%c\n", last_vowel);

    return 0;
}
*/


/*问题描述
　　给定一个整数，对这个整数的一次转换是指将这个整数变为这个整数的所有数位上的非零数字的乘积。
　　例如，对 123456789 进行一次转换变为 1*2*3*4*5*6*7*8*9=362880，再进行一次转换变为 3*6*2*8*8=2304，再进行一次转换变为 2*3*4=24，再进行一次转换变为 8。
　　给定一个整数，请依次将转换过程中经历的每个整数输出，直到小于 10 。
输入格式
　　输入一行包含一个整数 n 。
输出格式
　　输出多行，每行包含一个整数。
样例输入
123456789
样例输出
362880
2304
24
8
评测用例规模与约定
　　对于 50% 的评测用例，1 <= n <= 10**9 （10的9次方）。
　　对于所有评测用例，1 <= n <= 10**18 （10的18次方）。*/

//小数
/*#include <stdio.h>

int getDigitProduct(int n) {
    int product = 1;
    while (n > 0) {
        int digit = n % 10;
        if (digit != 0) {
            product *= digit;
        }
        n /= 10;
    }
    return product;
}

void printDigitProduct(int n) {
    while (n >= 10) {
        int product = getDigitProduct(n);
        printf("%d\n", product);
        n = product;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    printDigitProduct(n);

    return 0;
}
*/


/*
#include <stdio.h>

long long getDigitProduct(long long n) {
    long long product = 1;
    while (n > 0) {
        int digit = n % 10;
        if (digit != 0) {
            product *= digit;
        }
        n /= 10;
    }
    return product;
}

void printDigitProduct(long long n) {
    while (n >= 10) {
        long long product = getDigitProduct(n);
        printf("%lld\n", product);
        n = product;
    }
}

int main() {
    long long n;
    scanf("%lld", &n);

    printDigitProduct(n);

    return 0;
}
*/

//字符串 可处理大数   但是写的有问题
/*
#include <stdio.h>
#include <string.h>

void multiplyNonZeroDigits(char* str, int len) {
    long long product = 1;
    for (int i = 0; i < len; i++) {
        int digit = str[i] - '0';
        if (digit != 0) {
            product *= digit;
        }
    }
    printf("%lld\n", product);
}

void printDigitProduct(char* str) {
    while (strlen(str) > 1 || (strlen(str) == 1 && str[0] >= '1' && str[0] <= '9')) {
        multiplyNonZeroDigits(str, strlen(str));

        // 计算下一次的字符串
        char temp[10001];
        int tempIndex = 0;
        long long carry = 0;

        for (int i = 0; i < strlen(str); i++) {
            int digit = str[i] - '0';
            long long product = digit + carry * 10;
            temp[tempIndex++] = '0' + product / 2;
            carry = product % 2;
        }

        // 处理最后的进位
        while (carry > 0) {
            temp[tempIndex++] = '0' + carry % 2;
            carry /= 2;
        }

        // 倒置temp数组得到最终结果
        for (int i = 0; i < tempIndex; i++) {
            str[i] = temp[tempIndex - i - 1];
        }

        // 去掉前导零
        int start = 0;
        while (str[start] == '0' && start < tempIndex - 1) {
            start++;
        }

        // 更新字符串
        memmove(str, str + start, tempIndex - start);
        str[tempIndex - start] = '\0';
    }
}

int main() {
    char str[10001];
    scanf("%s", str);

    printDigitProduct(str);

    return 0;
}
*/


#include <stdio.h>

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int is_valid(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int dfs(int x, int y, int n, int m, int grid[][1000], int visited[][1000]) {
    visited[x][y] = 1;
    int count = 1;

    int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];

        if (is_valid(nx, ny, n, m) && !visited[nx][ny] && gcd(grid[x][y], grid[nx][ny]) > 1) {
            count += dfs(nx, ny, n, m, grid, visited);
        }
    }

    return count;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int grid[1000][1000];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    int r, c;
    scanf("%d %d", &r, &c);

    int visited[1000][1000] = { 0 };
    int result = dfs(r - 1, c - 1, n, m, grid, visited);

    printf("%d\n", result);

    return 0;
}



/*
#include <stdio.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    long long a[100000];
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    long long sum = 0;
    // 计算初始区间和
    for (int i = 0; i < k; i++) {
        sum += a[i];
    }

    long long maxSum = sum;

    // 滑动窗口，更新区间和
    for (int i = k; i < n; i++) {
        sum = sum - a[i - k] + a[i];
        if (sum > maxSum) {
            maxSum = sum;
        }
    }

    printf("%lld\n", maxSum);

    return 0;
}
*/


/*
#include <stdio.h>

// 函数声明
int gcd(int a, int b);
int is_valid(int x, int y, int n, int m);
int dfs(int x, int y, int n, int m, int grid[][1000], int visited[][1000]);

int main() {
    int n, m;
    printf("输入行数和列数：");
    scanf("%d %d", &n, &m);

    int grid[1000][1000];
    printf("输入网格元素：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    int r, c;
    printf("输入起始行和列：");
    scanf("%d %d", &r, &c);

    int visited[1000][1000] = { 0 };
    int result = dfs(r - 1, c - 1, n, m, grid, visited);

    printf("结果：%d\n", result);

    return 0;
}

// 最大公约数函数
int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 是否有效位置函数
int is_valid(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// DFS 函数定义
int dfs(int x, int y, int n, int m, int grid[][1000], int visited[][1000]) {
    visited[x][y] = 1;
    int count = 1;

    int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];

        if (is_valid(nx, ny, n, m) && !visited[nx][ny] && gcd(grid[x][y], grid[nx][ny]) > 1) {
            count += dfs(nx, ny, n, m, grid, visited);
        }
    }

    return count;
}
*/